package 图;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.ArrayDeque;
//import java.security.KeyStore.Entry;
import java.util.ArrayList;
/**
 * 最主要的 是 这个题 用 这种方式 来建图 和 解决 这真的是大材小用
 * 这里 采用的  是 一个 比较复杂 的 建图方式 
 * 还有 啥 链式 向前星 这种方式  
 * 去学习 一下
 * @author I adore you
 * 
 * 这个 建图  的 方式 就值得  吐槽一下  真他妈 离谱 等 建好图的 时候 别人 题都写完了
 *
 */

public class leetcode2039网络空闲时间 {
	
	public static void main(String args[]){
		int edges [][]= {{0,1},{1,2},{0,2}};
		int patience[] = {0,10,10};
		int [][] martix = {{0,1},{1,2},{2,4},{3,4},{0,3},{0,2}};
//		  测试       dfs
		solution(0,martix);
		
		
		
		
//		int ans  = solution(edges,patience);
//		System.out.println(ans);
//		System.out.println(getMinDis(generator(edges)));
//		System.out.println(Integer.MIN_VALUE);
	}
	
	public static int solution(int martix[][] ,int patience[]) {
		Graph graph =  generator(martix);
		HashMap<Node,Integer> disMap = getMinDis(graph);
//		int second = 0;
//		int ans = Integer.MAX_VALUE;
//		  把  0 编号的 代表的 节点 移掉
		disMap.remove(graph.nodes.get(0));
		int ans = Integer.MIN_VALUE;
		for(Node node : disMap.keySet()) {
//			if(disMap.containsKey(key)) {
//				
//			}
			int pi = patience[node.value];
			int transferTime =  disMap.get(node) * 2;
			if(transferTime <=pi) {
//				ans = transferTime;
				ans = Math.max(ans, transferTime);
			}
			else {
				int lastSendTime = (transferTime -1) / pi *pi;
				ans = Math.max(lastSendTime + transferTime, ans);
			}
			
		}
		return ans+1;
	}
	
/**
 * 对于 这种 无权图  什么 时无权图  就是 权值 是个 固定值  或者 为 1  这是我的理解
 * 采用  BFS 的 方式   来 建立 最短路径  的对应表 
 * 
 * 虽然  通过 了 但效率 真的 很差  差的 不是 一点半点  还是 很慢 但是  至少 能 ac 对吧  
 * 我感觉  慢主要   是 慢 在 建图的 方式  上面  用数组  肯定 比 用 哪些  复杂的 数据 结构 要 快啊对吧
 * 
 */
	public static HashMap<Node,Integer> getMinDis(Graph graph){
//		 这个哈希表  相当于 啥  dis 数组
		Node root = graph.nodes.get(0);
		HashMap<Node,Integer> disMap =new HashMap<>();
		disMap.put(root, 0);
//		 用来 记录 已经访问过的 节点    为啥 泛型 用  Integer 而不是 Node  会不会 快一些 啊 个人感觉
		HashSet<Integer> visited = new HashSet<>();
		Queue<Node> queue = new ArrayDeque<>();
		queue.add(root);
		while(!queue.isEmpty()) {
			Node node = queue.poll(); 
			for(Node cur : node.nexts) {
				if(!visited.contains(cur.value)) {
					disMap.put(cur, disMap.get(node) + 1);
					visited.add(cur.value);
					queue.add(cur);
				}
			}
			
		}
		
		
		return disMap;
	}
	
	public static void solution(int value,int martix[][]) {
//		Graph graph = generator(martix);  只需要 生成 这个图 就行  好像 不行   
	      Graph graph = generator(martix);
		HashSet<Node> set = new HashSet<>();
		Node  node  = graph.nodes.get(value);
		set.add(node);
		System.out.println(node.value);
		dfs(node,set);
	}
	public static void dfs(Node node,HashSet<Node> set) {
//		 if(node == null) {
//			 return ;
//		 }
		 for(Node cur :  node.nexts) {
			 if(!set.contains(cur)) {
				 set.add(cur);
				 System.out.println(cur.value);
				 dfs(cur,set);
			 }
		 }
		
		
	}
	
/**
 * 这个  方法 直接超时 了    数据 量 很大的时候 你这个 最短路径的 算法  就很 慢  因为 getMinNode
 *  是 暴力 遍历的 方式 进行 这就 很费时间 
 *  下面采用 堆 的方式 解决 
 *  这种方式 也失败了 我以为 可以用  系统的堆 来完成 这个题目 但事实上 是不行的 
 * @param root
 * @return
 */
/*
	public  static HashMap<Node,Integer> minDis(Node root){
		HashMap<Node,Integer> disMap  = new HashMap<>();
//		Graph graph = generator();
//		 使用 堆 来 getMinNode          
//		PriorityQueue<Node> queue = new PriorityQueue<>();
		Queue<Entry<Node,Integer>> queue = new PriorityQueue<>();
		HashSet<Node> selectNode = new HashSet<>();
		  disMap.put(root, 0);
//		  queue.add(root);
//		  queue.add(new Entry<>(root,0));
//		  queue.add();
//		  while(!queue.isEmpty()) {
//			  Node node = queue.poll();
			  int distance = disMap.get(node);
			  for(Edge edge  : node.edges) {
				  Node cur = edge.to;
//				     这说明 啥 啊  就是 root 到当前cur 节点的 距离 是无穷大对吧  也就是 没统计过当前节点
				  if(!disMap.containsKey(cur)) {
					  disMap.put(cur, Edge.weight + distance);
				  }
				  else {
//					   说明 root 到当前节点的 距离 已经 统计过  所以现在 要比较  存在的 距离 和curDistance  那个更小
					  disMap.put(cur,Math.min(disMap.get(cur), distance + Edge.weight));
				  }
//				  queue.add(e);
			  }
			  
			  
			  
		  }
		return disMap;
	}
	*/
//	  要明白 真个 流程 是 怎么 走的  就会 什么 清楚 代码 了       TLE
	public static HashMap<Node,Integer> minDistance(Node root){
		HashMap<Node,Integer> dis = new HashMap<>();
		dis.put(root, 0);
		HashSet<Node> selectNode = new HashSet<>();
		Node minNode  = getMinNode(dis,selectNode);
		while(minNode != null) {
			int distance = dis.get(minNode);
			for(Edge cur : minNode.edges) {
				Node to = cur.to;
				if(!dis.containsKey(to)) {
//					 添加 
					dis.put(to, distance+1);
				}
				else {
//					更新
					dis.put(to, Math.min(distance+1, dis.get(to)));
				}
			}
			selectNode.add(minNode);
			minNode =  getMinNode(dis,selectNode);
		}
		for(Entry<Node,Integer> entry : dis.entrySet()) {
			System.out.println(entry.getKey()+" "+entry.getValue());
		}
		return  dis;
	}
//	  暴力 遍历 所有的 节点 直接找出 当前 distanceMap 中 value 最小的节点
	public static Node getMinNode(HashMap<Node,Integer> dis,HashSet<Node> selectNode)  {
		Node minNode = null;
		int minDistance  = Integer.MAX_VALUE;
		for(Entry<Node,Integer> entry : dis.entrySet()) {		
			int distance = entry.getValue();
			Node node = entry.getKey();
			if(!selectNode.contains(node) && distance < minDistance) {
				minNode = node;
				minDistance = distance;
			}
//			selectNode.add(node); 要明白 什么 时候 把 该节点 锁死 肯定 不是在这个时候啊 
		}
				
		return minNode;		
	}
	
	
	public static Graph generator(int martix [][]) {
		Graph graph = new Graph();
		for(int i = 0;i < martix.length;i++ ) {
			int from =  martix[i][0];
			int to  =  martix[i][1];
			if(!graph.nodes.containsKey(from)) {
				graph.nodes.put(from, new Node(from));
			}
			if(!graph.nodes.containsKey(to)) {
				graph.nodes.put(to, new Node(to));
			}
/**
    注意 下面 这 些 代码  是不能  这样写  这样 写   会      出 问题 的 
  每次 都会 new 一个 地址  这样的  即使  数据项  相同    那么 地址  也不一样     
 */
//			Node fromNode = new Node(from);
//			Node toNode  = new Node(to);
			Node fromNode = graph.nodes.get(from);
			Node toNode = graph.nodes.get(to);
			fromNode.nexts.add(toNode);
			toNode.nexts.add(fromNode);
			Edge edge = new Edge(fromNode,toNode);
			Edge e2 = new Edge(toNode,fromNode);
			fromNode.edges.add(edge);
			toNode.edges.add(e2);
//			  这里 感觉不需要 判断
			graph.edges.add(edge);
			graph.edges.add(e2);
//	  这里 没有 入度   和    出度  		
		}
		return graph;
	}
	static class Graph{
		HashMap<Integer,Node> nodes;
		HashSet<Edge> edges;
		public Graph() {
			this.nodes = new HashMap<>();
			this.edges = new HashSet<>();
		}
	}
	static class Node{
		int value;
		ArrayList<Node> nexts;
		ArrayList<Edge> edges;
		public Node(int value) {
			this.value = value;
			nexts = new ArrayList<>();
			edges = new ArrayList<>();
		}
		public String toString () {
			return "value: "+value;
		}
		
	}
	static class Edge{
		Node from;
		Node to;
		public static final int weight = 1;
		public Edge(Node from,Node to) {
			this.from = from;
			this.to = to;
//			  这里的 边的权重  是一个  定值 就是  
//			weight = 1;
		}
		
	}
	
	
	

}
